package m202406.d20;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/20 22:16
 */
public class Q113 {


//    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
//        Stack<TreeNode> stack = new Stack<>();
//        stack.push(root);
//        Stack<Integer> op = new Stack<>();
//        int sum = 0;
//        List<List<Integer>> res = new ArrayList<>();
//        while (!stack.isEmpty()) {
//            TreeNode pop = stack.pop();
//            op.add(pop.val);
//            sum = sum + pop.val;
//            if (pop.right != null) {
//                stack.push(pop.right);
//            }
//            if (pop.left != null) {
//                stack.push(pop.left);
//            }
//            if (pop.left == null && pop.right == null ) {
//                if(sum == targetSum){
//                    res.add(new ArrayList<>(op));
//                }
//                op.pop();
//            }
////            op.pop();
//        }
//        return res;
//    }


    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        travel(root, 0, targetSum, new LinkedList<>(), list);
        return list;
    }


    private void travel(TreeNode node, int current, int target, LinkedList<Integer> list, List<List<Integer>> res) {
        if (node.left == null && node.right == null && current + node.val == target) {
            list.addLast(node.val);
            res.add(new ArrayList<>(list));
            list.removeLast();
            return;
        }
        if (node.left != null) {
            list.addLast(node.val);
            travel(node.left, current + node.val, target, list, res);
            list.removeLast();
        }
        if (node.right != null) {
            list.addLast(node.val);
            travel(node.right, current + node.val, target, list, res);
            list.removeLast();
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
